package sort;

public class MergeSort {	
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();
		list = IterativeSort(list);

		return System.currentTimeMillis()-startTime;
	}
	
	public static int[] IterativeSort(int[] list){
		//If list is small, just sort it with some simple algo
		if(list.length < 10) return InsertionSort.SortList(list);
		
		//else, split list into 2 equal parts and sort them for themselfs
		int[] a = new int[list.length/2], b = new int[list.length-a.length];
		if(list.length%2==1) b[b.length-1] = list[list.length-1];

		for(int i=0; i<list.length/2; i++) {
			a[i]=list[i<<1];
			b[i]=list[(i<<1)+1];
		}
		
		return Merge(IterativeSort(a), IterativeSort(b));
	}
	
	private static int[] Merge(int[] a, int[] b){
		int[] mergedList = new int[a.length + b.length];
				
		for(int i=0, aCount=0, bCount=0; i<mergedList.length; i++){
			if(bCount==b.length || (aCount<a.length && a[aCount] < b[bCount])) mergedList[i] = a[aCount++];
			else mergedList[i] = b[bCount++];
		}

		return mergedList;
	}
}
